//https://leetcode.cn/problems/find-all-anagrams-in-a-string/?envType=study-plan-v2&envId=top-100-liked
//1.滑动窗口；2.判断vec相等

#include <string>
#include <iostream>
#include <map>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 1; i < sLen - pLen+1; ++i) {
            --sCount[s[i-1] - 'a'];
            ++sCount[s[i + pLen-1] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i);
            }
        }

        return ans;
    }
};

class Solution2 {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();
        if (sLen < pLen) {
            return vector<int>();
        }
        vector<int> ans;
        std::map<char,int> ms;
        std::map<char,int> mp;
        for(auto c:p){
            ++mp[c];
        }
        
        for(size_t i=0;i<=s.size()-p.size();++i){
            if(i==0){
                int j=0;
                while(j<p.size()){
                    ++ms[s[j++]];
                }

            }else{
                --ms[s[i-1]];
                if(ms[s[i-1]] == 0) {
                    ms.erase(s[i-1]);
                }
                ++ms[s[i+p.size()-1]];
            }
            if(mp == ms) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};